package leetcodev1.链表;

public class LeetCode147 {

    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode sortedTail = head, index = head, sortedIndex;
        while (index != null) {
            ListNode node = index;
            index = index.next;
//            node.next = null;//清除尾链

            if (node.val < head.val) {
                node.next = head;
                head = node;
            } else if (node.val >= sortedTail.val) {
                sortedTail.next = node;
                sortedTail = node;
            } else {
                sortedIndex = head;
                while (sortedIndex != sortedTail) {
                    if (sortedIndex.val < node.val && sortedIndex.next.val > node.val) {
                        break;
                    }
                    sortedIndex = sortedIndex.next;
                }
                node.next = sortedIndex.next;
                sortedIndex.next = node;
            }
        }
        return head;
    }
}

class Answer147 {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode dummyHead = new ListNode(0);//虚拟节点
        dummyHead.next = head;
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;//continue
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;//先删除curr
                curr.next = prev.next;//连接比他大的节点
                prev.next = curr;//接上pre单节点
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}
